#include <iostream>

/*
Question:

have a string contains equal number of 'x' and 'z'. Remove all 'z' and append new 'x'
after each 'x'. Requirement: O(N) time complexity with O(1) space complexity.

Algorithm:

if the string is like "zzmxmx", we can easily convert it to be "mxxmxx" with O(N) time
and O(1) space. if it is "mxmxzz", we can do it reversely. Then how about "mxmxzzzzmxmx"?
we can split it to be two strings "mxmxzz" and "zzmxmx", make sure each substr contains
same number of 'x' and 'z', and always remove 'z' first, then we have enough space to double 'x'.
*/

using namespace std;

void ReplaceString( char* str, int start, int end, bool fromBeginning )
{
	int cur = 0;

	if( start>=end)
		return;

	if( fromBeginning )
	{
		cur = start;
		while( start<=end)
		{
			if( str[start] == 'x')
			{
				str[cur] = str[cur+1] = str[start];
				cur +=2;
			}
			else if( str[start] != 'z' )
			{
				str[cur] = str[start];
				cur++;
			}
			start++;
		}
	}
	else
	{
		cur = end;
		while( start<=end)
		{
			if( str[end] == 'x')
			{
				str[cur] = str[cur-1] = str[end];
				cur -=2;
			}
			else if( str[end] != 'z' )
			{
				str[cur] = str[end];
				cur--;
			}
			end--;
		}
	}
}

void ConvertString( char* str )
{
	int start=0;
	int end = 0;
	int len = strlen(str);
	int countX=0, countZ=0;

	for( end=0; end<len; end++ )
	{
		bool updateX = false;
		if( str[end] == 'x' )
		{
			countX++;
			updateX = true;
		}
		else if( str[end]=='z' )
			countZ++;
		if(countX && countX==countZ )
		{
			ReplaceString( str, start, end, updateX );
			start = end+1;
			countX = countZ = 0;
		}
	}
}

int main(void)
{
	char str[] = "mxmxzzzzmxmx";
	
	cout<<"before convert:"<<str<<endl;
	ConvertString(str);
	cout<<"after convert :"<<str<<endl;

	return getchar();
}